Consider a scenario where one network sends traffic into another network through a mutual attachment point. Mechanisms exist to measure the amount of congestion that this traffic is expected to cause downstream of the measuring point, by monitoring certain metrics that are all visible locally at the attachment point.
It is likely that a downstream network will want to use such a measurement of downstream congestion to in some way constrain the upstream network. For instance, the downstream network may wish to limit the amount of congestion that traffic from the upstream network can cause. It then becomes in the upstream network's interest to try to manipulate the metrics in the traffic in order to pervert the integrity of the measurements to its advantage. The present inventor has identified a need for a measurement technique that is robust to any manipulation by the upstream network to its advantage.
Some basic concepts will now be presented to facilitate understanding of the invention presented later on.
Packets
Data sources typically split the data they send into small units known as packets. A packet consists of a header and a payload. The great majority of packets carried by commercial networks nowadays are so-called Internet Protocol (IP) packets, which means they comply to the format specified in IETF RFC791 [see reference RFC791]. IP ensures the packets are correctly transmitted from the source to the destination. IP is a connectionless protocol—that means each packet carries sufficient information for any IP router to be able to forward it towards its destination without having had to previously set up any per-connection state in the router. Each packet could take a different route to reach the destination. In practice the routing mechanisms on the Internet mean that this seldom happens (unless there is some form of equipment failure).
Re-Feedback
One of the functions of a packet header such as the header of an IP packet is to accumulate information about the path it traverses on its way from the sender to the receiver. For instance, the time-to-live (TTL) field is decremented at every IP node or the explicit congestion notification (ECN [see reference: RFC3168]) field is probabilistically marked if the packet experiences congestion (see below). This path information allows nodes on the path to monitor characteristics of the path experienced so far (the upstream path). Typically mechanisms exist to allow the receiver to feed back this information to the sender.
International application WO2005/096566 describes a mechanism called re-feedback [see reference: [re-feedback]—details later], whereby the source re-inserts into the forward data path this information fed back to it by the receiver that had accumulated along the whole path. The sender may reinsert this information using a separate field in the packet header to that used to accumulate the original path metric or alternatively, it may initialise the value of the metric in the original field to a value that reflects the feedback it receives.
Any node along the path may then monitor the characteristics of the whole path at least a round trip ago. Given any node can already monitor the characteristics of the upstream path, it can subtract this froth the re-inserted whole path information to calculate an expectation of the characteristics of the downstream path (the rest of the path still to be traversed by packets it forwards).
Wherever measurements are taken in a network, the result of this subtraction should never be persistently negative, unless the source originally understated the whole path metric. International application WO2005/1109783 proposes using this fact for a mechanism to detect that a source is persistently understating a characteristic of the path in a flow of packets. The mechanism can sanction the flow accordingly to make it in the source's interests to correctly declare the whole path characteristic to the network. Thus the integrity of the re-inserted feedback information can be assured relative to the original feedback.
Distributed Bandwidth Sharing and Congestion
Data traversing the Internet follows a path between a series of routers, controlled by various routing protocols. Each router seeks to move the packet closer to its final destination. If too much traffic traverses the same router in the network, the router can become congested and packets start to experience excessive delays whilst using that network path. If sources persist in sending traffic through that router it could become seriously overloaded (congested) and even drop traffic (when its buffers overflow). If sources still persist in sending traffic through this bottleneck it could force more routers to become congested, and if the phenomenon keeps spreading, that can lead to a congestion collapse for the whole Internet—which occurred regularly in the mid-1980s.
The solution to that problem has been to ensure that sources take responsibility for the rate at which they send data over the Internet by implementing congestion control mechanisms. Sources monitor feedback from the receiver of the metric that characterises path congestion in order to detect when the path their data is following is getting congested, in which case they react by reducing their bit-rate. In the absence of any sign that the path is congested, they may slowly increase their rate.
The typical path characterisation metrics that sources monitor are the average roundtrip time (RTT) for the data path, the variance of the roundtrip time (jitter) and the level of congestion on the path. Congestion is one of the parameters controlling the rate adaptation of a source sending data over a congested path.
The congestion level can be signalled either implicitly (through congested routers dropping packets when their buffers overflow or to protect themselves) or explicitly (through mechanisms such as explicit congestion notification—see next subsection). Currently the most common option is implicit signalling. Historically, routers would drop packets when they got completely saturated (which happens when a traffic burst cannot be accommodated in the buffer of the router)—this policy is called Droptail. Random Early Detection (RED) [see reference: RED] is an improvement where routers monitor the average queue length in their buffer and when the average queue is higher than a given threshold, the router starts to drop packets with a probability which increases with the excess length of the queue over the threshold. It is widely used in today's Internet because it allows sources to react more promptly to incipient congestion and it keeps queues from growing unnecessarily long. Sources using TCP are able to detect losses, because a packet loss causes a gap in the sequence; whenever a TCP source detects a loss, it is meant to halve its data transmission rate, which alleviates the congestion on the router at the bottleneck.
Explicit Congestion Notification
Explicit Congestion Notification (ECN) [see reference: RFC3168] further improves on RED by using a two-bit ECN field in the IP header to signal congestion. It runs the same algorithm as RED, but instead of dropping a packet, it sets its ECN field to a Congestion Experienced (CE) codepoint. The ECN standard requires the sender to echo any congestion mark signalled in the data; for instance, a TCP receiver sets an Echo Congestion Experienced (ECE) flag in the TCP header, which the TCP source interprets as if the packet has been dropped for the purpose of its rate control. In turn the source then reacts to the congestion by halving its transmission rate and notifies the receiver of this using a Congestion Window Reduced codepoint.
The four values of the two-bit ECN field in the IP header are:                “Non ECT”, which signifies that the packet belongs to a flow that doesn't support ECN;        “ECT(0)” and “ECT(1)”, which signify that the packet belongs to a flow that supports ECN and that upstream routers haven't had to mark the packet; and        “Congestion Experienced” (CE) which signals that a packet has experienced incipient congestion.Re-ECN        
Re-ECN [see reference: re-ECN] is an example of a system that utilises re-feedback to provide upstream and downstream congestion information throughout the network. It is similar to ECN but uses an extra unused bit in the packet header. This bit is combined with the two-bit ECN field to create four extra codepoints.
The simplest way to understand the protocol is to think of each packet as having a different flag (or codepoint) indicating how much the bytes in the packet are worth. At the start of a flow, a cautious flag is used to indicate that the sender does not have sufficient knowledge of the path and all the bytes in the packet are worth +1. Cautious flags are also used whenever the sender becomes unsure about the current state of the path.
By default packets are marked with Neutral flags which indicate that the bytes in the packet are worth zero. If packets encounter congestion during their progress through the network the ECN marking applied by the congested router are considered as Negative flags that make the bytes in the marked packets worth −1. The destination will feed back a count of the number of Negative flags it has seen. For every Negative flagged byte it is informed of, the sender should mark an equivalent number of bytes it sends in a subsequent packet or packets with a Positive flag, which makes all the bytes in that packet worth +1. The Positive flag re-echoes or reinserts the congestion feedback back into the forward-travelling stream of packets, hence the name re-ECN. These Positive flags will not be modified by the network once they are set by the sender.
If a packet has a Positive flag it will sometimes be termed a Positive packet. If it has a Negative flag, it will be termed a Negative packet, and so forth.
There is a small possibility that a Positive packet will in turn be marked Negative by a congested router, but the encodings are chosen so that the original Positive marking survives as well—the bytes in packets with both Positive and Negative markings are considered worth 0 and these packets are described as Cancelled.
At any intermediate node the upstream congestion is given by the proportion of Negative flagged bytes to total bytes. Thus the continually varying congestion level is effectively encoded in a stream of packets by interpreting the stream of Negative or non-Negative (Neutral) markings as a unary encoding of ones or zeroes respectively. Similarly, the congestion level of the whole path is encoded as a stream of Positive or non-Positive (Neutral) markings. The expected downstream congestion from any intermediate node can then be estimated from the difference between the proportion of Positive flags and the proportion of Negative flags, as described in International application WO2006/079845. The difference between the proportions of flags in these two sequences can be thought of as a third virtual sequence of flags on the packets, representing downstream congestion. However, these virtual flags only result from a mathematical operation (subtraction); they do not physically appear on packets.
Congestion Exposure (ConEx)
In June 2010, the Internet Engineering Task Force (IETF) chartered a new Congestion Exposure (ConEx) working group to add re-feedback of path congestion to the Internet Protocol (IP—initially IPv6) and to make the necessary modifications to the Transmission Control Protocol (TCP), both as experimental standards. The ConEx protocol will be based on the re-ECN protocol, but it will be slightly different because it is required to be usable independently of ECN, although it is recognised that its full benefit is only possible with ECN see reference: [conex-mech].
The final form of the ConEx protocol to be standardised by the IETF is not yet determined. Therefore in this specification the re-ECN protocol will be used as a concrete embodiment, given it has been fully specified and implemented.
Perverting the Integrity of Downstream Path Characteristics
It has been recognised in section 4.4 of [re-ecn-motive] that, if downstream path characterisation is calculated by taking the difference between two superimposed unary encodings such as is disclosed in WO2006/079845, it seems possible to pervert the integrity of this characterisation. An example scenario will now be described using FIG. 1, then it will be used to show the potential extent of this problem.
A data sender “S” 11 is attached to a network such as a data centre 10 both of which may be owned by the same data centre operator. The data centre, is in turn attached to an access network 20 via a network attachment node “Na” at an attachment point 13. (i.e., connection point including an active electronic device that is attached to a network and is capable of creating, receiving . or transmitting information over a communication channel). A data receiver “R” 19 attaches to the same access network at a network attachment node at attachment point 17. Network 1U includes routers 15. Network 20 includes routers 25.
For the purpose of this explanation, FIG. 1 shows a single end-to-end path 12 (see “Key to Schematic”), along which packets flow from sender “S” 11 to receiver “R” 19. From the point of view of the network attachment node “Na” at attachment point 13, this end-to-end path 12 comprises an upstream portion 12a (extending from sender “S” 11 via one or more of routers 15 of network 10 to attachment point 13) and a downstream portion 12b (extending from attachment point 13 via one or more of routers 25 of network 20 and attachment point 17 to receiver “R” 19). It will be understood that packets travelling from sender “S” 11 to receiver “R” 19 need not all traverse the same path, and that the division between “upstream” and “downstream” on any path will depend on the entity from whose point of view the path is to be regarded. The following explanation would be applicable in relation to other more complex scenarios, but in the interests of clarity, this simple scenario will be used.
As the data centre network 10 forwards packets across the border with the access network 20, the access network monitors the re-ECN protocol fields in packets passing the attachment point 13. The function at the attachment point consists of a border monitor that measures the level of downstream congestion and some other function that acts on what it measures. It might limit the amount of downstream congestion that the data centre network can cause in the access network, as is discussed in International application WO2006/082443, and in reference [Jacquet08]. Alternatively, it might trigger various management actions, or it may send the measurements to an accounting system in order to levy charges.
Normally, the access network would count arriving Positive packets to measure downstream congestion. It might expect to see a few Negative packets due to congestion within the data centre, but probably not many. It would subtract the bytes in these few Negative packets from the count of bytes in Positive packets to calculate how much congestion remained on the rest of the path, rather than in the data centre.
FIG. 2 represents a certain volume of transmitted data by the area of a square. The square is shown divided into areas horizontally to represent the proportions of packets marked by congested network elements (Negative) or not (Neutral). The square is also shown divided into areas vertically to represent the proportions of packets marked by the sender to expose whole-path congestion to the network (Positive) or not (Neutral).
FIG. 2 shows a typical scenario, where there is 1.00% congestion in the access network and only 0.70% congestion in the data centre network. Therefore, when traffic arrives at the border of the access network (top centre square), 0.70% of packets will already have been flagged Negative by the data centre network, leaving 99.30% unmarked (Neutral).
The congestion marking algorithm in network equipment is deliberately designed so that packets can be marked randomly without regard to what marking any particular packet already has. Therefore, by the time packets reach receiver R, a further 1.00% of the Neutral packets will have been marked Negative, that is 1.00% of 99.30%=0.99% more Negative packets added to the 0.70% already flagged Negative, which adds up to 1.69% Negative packets at the destination (all percentage figures are given accurate to two decimal places). These proportions of markings are illustrated graphically (but not to scale) in the top row of FIG. 2.
The receiver R will send feedback to the sender that 1.69% of packets have arrived with the Negative “congestion experienced” (CE) flag set. Then, in compliance with the re-ECN protocol, the sender S will set the Positive flag on the same proportion (i.e. 1.69%) of packets (bottom left of FIG. 2). As the mixture of Positive and non-Positive (Neutral) packets passes through the two networks, they will also be flagged Negative to indicate the congestion they experience. If, for the purposes of illustration, we assume that the congestion level remains stable, these packets will experience the same level of congestion in each network as before. Given that the Negative and Positive signals can be set independently, this will lead to the data centre network congestion marking 0.70% of the Neutral packets and 0.70% of the Positive packets. That will result in 0.70% of the 1.69% of packets that start out flagged Positive being flagged Negative as well. Thus about 0.01% of packets will be marked both Positive and Negative. As already explained, such packets are termed Cancelled because the Positive marking that indicates whole path congestion is “cancelled-out” by the Negative marking that indicates upstream congestion on the same packet.
Of the other 98.31% of packets that start out unmarked (Neutral), 0.7% will be marked Negative, that is 0.69% of all packets arriving at the access network will be Negative. Given that 1.69% of packets were originally Positive and the data centre marks 0.01% Negative, that will leave 1.68% marked Positive on arrival at the access network.
The attachment point at the ingress to the access network can then subtract the proportion of Positive packets (1.68%) from the proportion of Negative packets (0.69%) to estimate that downstream congestion is (1.68%-0.69%)=0.99%, which is a reasonable estimate of the actual congestion downstream of this attachment point, which (it will be recalled) is 1.00%.
Although the data centre scenario of FIG. 1 is used to illustrate vulnerabilities in the re-ECN protocol, of course, similar attacks could be mounted by any network (or other such entity) forwarding packets to any other network. The data centre network mounting the attacks could just as easily be a home network, a University network or one commercial network forwarding packets to another commercial peer.
Whatever the scenario, the markings on the packets will always be under the control of the upstream network until the packets are handed over at the attachment point between the networks. It will always be in an upstream network's interest in relation to issues of congestion accountability at least) to try to make the measured level of downstream congestion appear as if it is less than in reality. A robust technique is required that can reliably measure congestion downstream of the attachment point and that can be verified to the satisfaction of both parties, even though the upstream network could have altered the packet markings beforehand.
Attack Strategy #1: Extreme Upstream Congestion
Returning to the example data centre scenario of FIG. 1, if the data centre sets both Positive and Negative flags on nearly all packets, it seems to be able to pervert the access network's measurement of downstream congestion to its advantage. The following example illustrates the outcome of this strategy. Imagine there is still 1.00% congestion in the access network downstream of the data centre network. The data centre network can pretend that congestion is very high within the data centre, perhaps marking 90.91% of packets as Negative, as shown in FIG. 3. Then when the access network marks 1.00% of packets Negative it will result in 91.00% Negative packets, because the data centre only leaves 9.09% of packets not Negative, which when marked by the access network with 1.00% probability will only add 0.09% Negative packets, resulting in 91.00% Negative packets.
The data centre can comply with the re-ECN protocol by flagging 91.00% of packets as Positive at the source, but also continuing to mark 90.91% of packets Negative, which is unusual but not contrary to any protocol. Only the 9.00% of packets originally left unmarked (Neutral) can become Negative. Therefore, only 8.18% will be flagged Negative at the border with the access network. The much larger proportion (91.00%) of packets flagged Positive will result in a much larger proportion (82.73%) of packets Cancelled (i.e. flagged both Positive and Negative) arriving at the border with the access network, leaving only 8.27% still Positive.
Once these Positive packets pass through the 1% congestion-marking in the access network, 8.19% will be left Positive, which will correctly match the 8.19% proportion of packets that are Negative. Therefore the access network cannot complain that the traffic is non-compliant with the re-ECN protocol, because nowhere will there be insufficient Positive bytes relative to Negative.
However, when the access network subtracts Negative from Positive bytes as packets arrive from the data centre, it will measure downstream congestion as 8.27%-8.18%=0.09%. Whereas the actual value should be 1.00%. Thus, by introducing a very high amount of (apparent) congestion in its own network and otherwise complying with the letter of the re-ECN protocol, the data centre has managed to make the access network think that data centre traffic is causing only 0.09% congestion in the access network, which is eleven time less than the 1.00% congestion it is actually causing.
Attack Strategy #2: Signal Poisoning with Both Markings
In a second strategy to pervert the access network's measurement of downstream congestion, the operator of the data centre network (10 in FIG. 1) could use the re-ECN protocol as normal, but in addition arrange for the sender S to mark a high proportion of all packets as Cancelled (i.e. flagged both Positive and Negative). An example of this attack is shown in FIG. 4, where the sender S starts by flagging 34.00% of packets as Cancelled.
The Positive flags on these packets do not contribute to any measurement of downstream congestion, because they are all Cancelled out by the Negative flags on the same packets. Also, these packets are immune to further congestion marking because thy are already marked Negative. It can be seen from FIG. 4 that the data centre operator can still apply the re-ECN protocol to the remaining 66.00% of packets. If the access network operator subtracts Negative from Positive markings in the packets it receives from the data centre network it will measure downstream congestion as 66.00% of its actual value, that is 0.66% rather than 1.00%. Thus the upstream network can reduce the level of congestion that the access network measures by effectively “poisoning” the re-ECN signal with Cancelled packets.
Attack Strategy #3: Switching Negative Markings
It has been proposed in [re-ECN.motivation] that a border monitor could negate attack strategy #2 when calculating downstream congestion by using the following formula to calculate downstream congestion:Downstream congestion=Cancelled bytes+Positive bytes−Negative bytes  (1)
In other words, this approach counts bytes in Cancelled packets in addition to those solely marked Positive before subtracting bytes in packets marked Negative. Both strategies #1 and #2 introduce a large proportion of Cancelled packets, so counting these as Positive would appear to negate these attacks.
However, if the operator of the upstream network (e.g. the data centre network in FIG. 1) suspects that the border monitor is using this approach, it can adopt a counter-strategy, termed attack strategy #3, that still reduces the apparent level of downstream congestion given by equation (1). The upstream network can guarantee to make downstream congestion appear lower if it switches Negative markings from Cancelled packets to unmarked (Neutral) packets. This approach ensures that traffic still complies with the re-feedback condition that there must not be more Negative than Positive traffic, because it increases the proportion of Positive packets and the proportion of Negative packets by the same amount.
If a downstream network includes Cancelled packets in its calculation of downstream congestion, it is advantageous to an upstream network to reduce the proportion of Cancelled packets, whereas attack #2 showed that when the downstream network does not include Cancelled packets in its calculations it is advantageous for the upstream network to increase the proportion of Cancelled packets.
In typical circumstances where low levels of congestion prevail the proportion of Cancelled packets will be very small. For instance, it would be unusual for congestion to be higher than in the scenario of FIG. 2 where total congestion is 1.69%, and in that case only 0.01% of packets end up as Cancelled. Therefore, given attack strategy #3 consumes Cancelled packets, this attack only seems able to achieve a very small reduction in downstream congestion. Attack strategy #3 can however be combined with strategy #1, to greatly reduce apparent downstream congestion—by up to half of its actual value. Strategy #1 greatly increases the proportion of Cancelled packets, giving plenty to switch from Cancelled to Neutral using strategy #3.
FIG. 5 illustrates a numerical example of this combined attack. First (top centre), the data centre applies strategy #1, faking a high 49.49% level of congestion, which results in 50.00% Negative markings (top right) once it has also passed through congestion in the access network, which is still 1.00% as in previous examples.
The sender S initially complies with the re-ECN protocol by marking 50.00% of packets Positive (bottom left). Once all the sender's packets have been subjected to the same 49.49% fake congestion, the proportions marked Cancelled and Negative will both be about 24.75% (percentages accurate to 2 decimal places). Then the data centre network applies strategy #3; it switches the Negative markings from most of the Cancelled packets onto art equal amount of unmarked (Neutral) traffic. In FIG. 5 (bottom centre) it has chosen to switch 24.70% of packets, so the proportion of Positive packets and Negative packets increases by 24.70%.
When the access network uses equation (1), the data centre network has successfully fooled it into calculating that downstream congestion is 0.55% rather than 1.00%, a reduction by nearly one half. These combined attacks still comply with the constraint of the re-feedback protocol that there must be no more Negative packets than Positive, because it can be seen in FIG. 5 (bottom right) that Negative and Positive packets end up equal as required.